package com.duoduo.字符串;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。5
 *
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * hot 5
 */
public class 最长回文子串 {
    public static String longestPalindrome2(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        //中心扩展算法
        //从每一个位置mid出发，向两边扩散
        int maxStart=0;//记录最长回文子串的起点
        int maxLen=0;//记录最长回文子串的长度
        int left = 0;
        int right = 0;
        int len = 1;
        for (int i = 0; i < s.length(); i++) {
             left=i-1;
             right=i+1;
            //向左侧扩展，直到超过边界或遇到与中心字符不等跳出while循环
            while (left>=0 && s.charAt(left)==s.charAt(i)){
                left--;
                len++;
            }
            //向右侧扩展，直到超过边界或遇到与中心字符不等跳出while循环
            while (right<s.length() && s.charAt(right) == s.charAt(i)){
                right++;
                len++;
            }
            //同时向左右两侧扩展
            while (left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
                //注意此处，在最后一次循环中，即最长回文子串索引为：i~j，此时的left=i-1，right=j+1
                left--;
                right++;
                len = len + 2;
            }
            if (len>maxLen){
                maxStart=left;
                maxLen=len;
            }
            len=1;
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);
    }
    public static  String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int maxStart=0,maxEnd=0;
        for (int i = 0; i < s.length(); i++) {
            int charCenterLen=expandAroundCenter(s,i,i);
            int blackCenterLen=expandAroundCenter(s,i,i+1);
            int len=Math.max(charCenterLen,blackCenterLen);
            if (len>maxEnd-maxStart){
                maxStart=i-(len-1)/2;
                maxEnd=i+len/2;
            }
        }
        return  s.substring(maxStart,maxEnd+1);
    }
    private  static int expandAroundCenter(String s,int left,int right){
        while (left>=0 && right<s.length() && s.charAt(left) ==s.charAt(right)){
            left--;
            right++;
        }
        return  right-left-1;
    }

    public static void main(String[] args) {
        String babad = longestPalindrome2("cbbd");
        System.out.printf(babad);


    }
}
